Shortest Palindrome using KMP (LPS Array)

Finding the longest palindromic prefix to minimize prepended characters.

📝 Problem & KMP String Setup

The shortest palindrome is achieved by finding the **Longest Proper Prefix of $S$ that is already a palindrome**. This prefix should not need any characters prepended.

The KMP solution requires creating a special string $S'$:

$S' = S + \# + S^R$

($S$ = Original String, $S^R$ = Reversed String, $\#$ = Unique Separator)

Input Section

Concatenated String ($S'$):

💡 LPS Array Key Insight

The Goal: Find Longest Palindromic Prefix (LPP)

The LPP of $S$ is the longest prefix of $S$ that matches a suffix of $S^R$.

How LPS Helps:

  1. The KMP LPS array calculates the length of the longest **prefix** of $S'$ that is also a **suffix** of the current substring $S'[0\dots i]$.
  2. When computing the LPS array for $S' = S + \# + S^R$, the comparisons are effectively matching the prefix of $S$ (the prefix of $S'$) against a suffix of $S^R$ (the suffix of $S'$).
  3. The value of the **last element** of the LPS array, $\text{LPS}[|S'|-1]$, gives the length ($L$) of the longest prefix of $S$ that forms a palindrome with a suffix of $S$.

Construction Formula:

If the final $\text{LPS}$ value is $L$ (Length of Longest Palindromic Prefix), the characters that need to be prepended come from the beginning of $S^R$ (or the end of $S$).

Characters to Prepend = $S^R[\text{0} \dots |S|-L-1]$

🎬 Step-by-Step LPS Array Computation

LPS array computation initialized. Click 'Next Step' to begin.

String $S'$ and LPS Array $\pi$

Indices (i)
String ($S'$)
LPS Array ($\pi[i]$)

**Current State:** Index $i=?$, LPS Pointer $\text{len}=?$

Output Log


            

        


        

            
🎉 Final Shortest Palindrome

            
            

                
The length of the Longest Palindromic Prefix (LPP) is the final value of the LPS array:

                
$L = \text{LPS}[|S'|-1] = ?$

            


            
Characters to Prepend

            
Characters required: $|S| - L = ? - ? = ?$ characters.

            

                

            
            
The Shortest Palindrome:

            

                ?